//
//  BinaryTree.swift
//  others
//
//  Created by lhc on 2024/8/26.
//

import Foundation



/// 二叉树
class BinaryTree<T: Comparable, E> {
    
    class Node {
        enum Color {
            case red
            case black
        }
        
        var left: Node?
        var right: Node?
        var key: T
        var value: E?
        var height = 1
        var color = Color.red
        
        init(key: T, value: E? = nil) {
            self.key = key
            self.value = value
        }
    }
    
    internal var size = 0
    internal var root: Node? = nil
    
    func getSize() -> Int {
        return self.size
    }
    
    func isEmpty() -> Bool {
        return self.size == 0
    }
    
    /// 查找二叉树中是否有key的node
    func contains(key: T) -> Bool {
        guard !self.isEmpty() else {return false}
        
        return self.contains(key: key, node: self.root)
    }
    
    private func contains(key: T, node: Node?) -> Bool {
        guard let node = node else {return false}
        
        if key < node.key {
            return self.contains(key: key, node: node.left)
        }else if key > node.key {
            return self.contains(key: key, node: node.right)
        }
        // key == node.key
        return true
    }
    
    ///  前序遍历
    func preOrder(action: (T, E?)->()) {
        self.preOrder(node: self.root, action: action)
    }
    
    private func preOrder(node: Node?, action: (T, E?)->()) {
        guard let node = node else {return}
        
        action(node.key, node.value)
        self.preOrder(node: node.left, action: action)
        self.preOrder(node: node.right, action: action)
    }
    
    /// 检查当前树中序遍历是否符合从小到大排序性质
    func isBinaryTree() -> Bool {
        
        var resultList = [T]()
        self.inOrder { key, value in
            resultList.append(key)
        }
        for i in 1..<resultList.count {
            if resultList[i] < resultList[i - 1] {
                return false
            }
        }
        return true
    }
    
    /// 中序遍历
    func inOrder(action: (T, E?)->()) {
        self.inOrder(node: self.root, action: action)
    }
    
    private func inOrder(node: Node?, action: (T, E?)->()) {
        guard let node = node else {return}
        
        self.inOrder(node: node.left, action: action)
        action(node.key, node.value)
        self.inOrder(node: node.right, action: action)
    }
    
    /// 后序遍历
    func postOrder(action: (T, E?)->()) {
        self.postOrder(node: self.root, action: action)
    }
    
    private func postOrder(node: Node?, action: (T, E?)->()) {
        guard let node = node else {return}
        
        self.postOrder(node: node.left, action: action)
        self.postOrder(node: node.right, action: action)
        action(node.key, node.value)
    }
    
    /// 通过key查找node
    func getWithKey(_ key: T) -> Node? {
        guard !self.isEmpty() else {return nil}
        
        return self.getWithKey(key, node: self.root)
    }
    
    private func getWithKey(_ key: T, node: Node?) -> Node? {
        guard let node = node else {return nil}
        
        if key < node.key {
            return self.getWithKey(key, node: node.left)
        }else if key > node.key {
            return self.getWithKey(key, node: node.right)
        }
        
        // key == node.key
        return node
    }
    
    /// 返回最小key的node
    func miniNode() -> Node? {
        if self.isEmpty() {
            return nil
        }
        
        return self.miniNode(node: self.root!)
    }
    
    internal func miniNode(node: Node) -> Node {
        if let left = node.left {
            return self.miniNode(node: left)
        }
        
        // left == nil
        // 当前node是最小node
        return node
    }
    
    func maxNode() -> Node? {
        if self.isEmpty() {
            return nil
        }
        
        return self.maxNode(node: self.root!)
    }
    
    private func maxNode(node: Node) -> Node {
        if let right = node.right {
            return self.maxNode(node: right)
        }
        
        // right == nil
        // 当前node是最大node
        return node
    }
}
